UC知道C++厉害的来啊``急
来源：百度知道 编辑：UC知道 时间：2024/06/04 20:20:21
题目：阅读以下二叉树操作算法，回答相关问题。（补充：最好用C++来写）
void unkonwn (BinTreeNode* t)
BinTreeNode *p=t,*temp;
if(p!=NULL)
{
temp=p→leftChild;
p→leftChild=p→rightChild;
p→rightChild=temp;
unkonwn(p→leftChild);
unkonwn(p→leftChild);
}
}
(1)指出该算法完成什么功能；
（2）设计一个算法，不用栈将以上算法中的第二个递归语句消去；
（3）设计一个算法，ADT栈将以上算法改写成非递归。
ADT栈的函数有：
makeEmpty(s); 置栈S为空栈
push(S,value);新元素value进栈S
pop(S); 出栈
isEmpty(S); 判断栈S是否为空
void unkonwn (BinTreeNode* t)
BinTreeNode *p=t,*temp;
if(p!=NULL)
{
temp=p→leftChild;
p→leftChild=p→rightChild;
p→rightChild=temp;
unkonwn(p→leftChild);
unkonwn(p→leftChild);
}
}
(1)指出该算法完成什么功能；
（2）设计一个算法，不用栈将以上算法中的第二个递归语句消去；
（3）设计一个算法，ADT栈将以上算法改写成非递归。
ADT栈的函数有：
makeEmpty(s); 置栈S为空栈
push(S,value);新元素value进栈S
pop(S); 出栈
isEmpty(S); 判断栈S是否为空
(1)
void unkonwn (BinTreeNode* t)
{
BinTreeNode *p=t,*temp;
if(p!=NULL)
{
temp=p→leftChild;
p→leftChild=p→rightChild;
p→rightChild=temp;
unkonwn(p→leftChild);
unkonwn(p→rightChild); //是不是右结点？
}
}
将二叉树的左右结点互换。
(2)
void unkonwn (BinTreeNode* t)
{
BinTreeNode *p=t,*temp;
if(p!=NULL)
{
temp=p→leftChild;
p→leftChild=p→rightChild;
p→rightChild=temp;
//替换 unkonwn(p→leftChild);
BinTreeNode *l=p→leftChild;
while(l!=NULL)
{
temp=l→leftChild;
l→leftChild=l→rightChild;
l→rightChild=temp;
unkonwn(p→rightChild);
}
unkonwn(p→rightChild);
}
}
(3)非递归算法
void unkonwn (BinTreeNode* t)
{
BinTreeNode *p=t,*temp;
makeEmpty(s);
do
{
while(p!=NULL)
{
temp=p→leftChild;
p→leftChild=p→rightChild;
p→rightChild=temp;
push(